package test;

import java.util.Scanner;

/**
 * @author sunzhuokun
 * @date 14:11 2024/5/14
 * @description 高效的任务规划
 * 你有 n 台机器，编号为 1~n，每台都需要完成一项工作，机器经过配置后都能完成独 立完成一项工作。 。假设第 i 台机器你需要花 B 分钟进行设置，然后开始运行，
 * J 分钟后完成任务。 。现在，你需要选择布置工作的顺序，使得用最短的时间完成所有工作。 。
 * 注意，不能同时对两台进行配置，但配置完成的机器们可以同时执行他们各自的工作.
 * <p>
 * 输入描述
 * <p>
 * 第一行输入代表总共有 M 组任务数据 (1<M<=10)。 。
 * 每组数第一行为一个整数指定机器的数量 N (0<N<=1000)。
 * 随后的 N 行每行两个整数，第一个表示 B (0<=B<=10000)，第二个表示 J (0<=J<=10000)
 * <p>
 * 每组数据连续输入，不会用空行分隔。各组任务单独计时。
 * <p>
 * 输出描述
 * <p>
 * 对于每组任务，输出最短完成时间，且每组的结果独占一行。例如，两组任务就应该有
 * <p>
 * 两行输出
 * <p>
 * 使用贪心算法解
 * <p>
 * 示例1：
 * 1
 * 2
 * 1 1
 * 2 2
 * 输出：4
 * <p>
 * 示例2：
 * 2
 * 2
 * 1 1
 * 2 2
 * 3
 * 1 1
 * 2 2
 * 3 3
 * 输出：
 * 4
 * 7
 */
public class TaskPlanning_高效的任务规划 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 任务数
        int M = scanner.nextInt();
        for (int m = 0; m < M; m++) {
            // 机器的数量
            int N = scanner.nextInt();
            // 机器的配置时间和运行时间
            int[][] machines = new int[N][2];
            for (int i = 0; i < N; i++) {
                // 配置时间 B
                machines[i][0] = scanner.nextInt();
                // 运行时间 J
                machines[i][1] = scanner.nextInt();
            }
            // 按照运行时间 J 降序排序
            for (int i = 0; i < N - 1; i++) {
                for (int j = 0; j < N - 1 - i; j++) {
                    if (machines[j][1] < machines[j + 1][1]) {
                        int[] temp = machines[j];
                        machines[j] = machines[j + 1];
                        machines[j + 1] = temp;
                    }
                }
            }
            // 计算最短完成时间
            int time = 0;
            for (int i = 0; i < N; i++) {
                int B = machines[i][0];
                int J = machines[i][1];
                if (i == 0) {
                    time = B + J;
                } else {
                    // 如果当前机器的配置时间加上运行时间小于当前的总时间，则同时运行
                    // 假设并行之前机器的运行时间后的运行时间 之前的总时间 - 之前的运行时间 + 当前的配置时间 + 当前的运行时间
                    time = Math.max(time, time - machines[i - 1][1] + B + J);
                }
            }
            System.out.println(time);
        }
        scanner.close();
    }
}
